// m

// 给定一个m * n的有序二维矩阵matrix，矩阵中每行元素从左到右升序排列，每列元素从上到下升序排列，再给定
// 一个目标值target，要求判断矩阵中是否存在目标值target

function searchMatrix(matrix, target) {
    let rows = matrix.length
    if (rows === 0) {
        return false
    }
    let cols = matrix[0].length
    if (cols === 0) {
        return false
    }
    let min_val = Math.min(rows, cols)
    let index = diagonalBinarySearch(matrix, min_val - 1, target)
    if (matrix[index][index] === target) {
        return true
    }
    for (let i = 0; i <= index; i++) {
        let row_search = rowBinarySearch(matrix, i, cols - 1, target)
        let col_search = colBinarySearch(matrix, i, rows - 1, target)
        if (row_search || col_search) {
            return true
        }
    }
    return false
}

function diagonalBinarySearch(matrix, diagonal, target) {
    let left = 0
    let right = diagonal
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        if (matrix[mid][mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

function rowBinarySearch(matrix, begin, cols, target) {
    let left = begin
    let right = cols
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        if (matrix[begin][mid] < target) {
            left = mid + 1  
        } else if (matrix[begin][mid] > target) {
            right = mid
        } else {
            left = mid
            break
        }
    }
    return left >= begin && left <= cols && matrix[begin][left] === target
}

function colBinarySearch(matrix, begin, rows, target) {
    let left = begin + 1
    let right = rows
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2)
        if (matrix[mid][begin] < target) {
            left = mid + 1
        } else if (matrix[mid][begin] > target) {
            right = mid
        } else {
            left = mid
            break
        }
    }
    return left >= begin && left <= rows && matrix[left][begin] === target
}

let matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]

let matrix2 = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

console.log(searchMatrix(matrix, 3))
console.log(searchMatrix(matrix2, target))